#include "global.h"
#include <stdio.h>
#include <string.h>
#include <cstdio>

#include "collapsing.h"

#define MAX_NO_OF_NODES 128
#define MAX_LENGTH_OF_TITLE 256

struct hypergraph {
  int noOfNodes;
  char nodeName[MAX_NO_OF_NODES][MAX_LENGTH_OF_TITLE];

  int noOfEdges;
  int edgeDimension[MAX_NO_OF_NODES];
  int edge[MAX_NO_OF_NODES-1][MAX_NO_OF_NODES];
  int edgeName[MAX_NO_OF_NODES];//[MAX_LENGTH_OF_TITLE];

  int noOfRelatedNodes[MAX_NO_OF_NODES];
  int relatedNodes[MAX_NO_OF_NODES][MAX_NO_OF_NODES];

  int sequenceLength;
  int sequence[MAX_NO_OF_NODES-1];
  int noOfCollapsedNodes[MAX_NO_OF_NODES];
  int collapsedNodes[MAX_NO_OF_NODES-1][MAX_NO_OF_NODES];
};

static struct hypergraph g;
static vector< vector<int> > history;
static int sequenceIndex;
static int serialNumber;

void initializeGraph( struct hypergraph *g);
//void fillGraph( struct hypergraph *g);
int testOne( struct hypergraph *g);
int testTwo( struct hypergraph *g);
int testThree( struct hypergraph *g);
int findNext2DEdge( int seed, struct hypergraph *g);
int findInitialCollapse( struct hypergraph *g);
void collapse2DEdge( int e, struct hypergraph *g);
int findNextCollapse( struct hypergraph *g);
void decollapseLast2DEdge( struct hypergraph *g);
void output( struct hypergraph *g);
void putCollapseInSequence( struct hypergraph *g);

  
void printA( struct hypergraph *g) {
  int a, b;
  printf("related\n");
  for (a=0; a < 4;a++){
    for (b=0;b<3; b++){
      printf(" %d", g->relatedNodes[a][b] );
    }
    printf("      %d \n", g->noOfRelatedNodes[a]);
  }
  printf("\n");
}

void printB( struct hypergraph *g) {
  int i, j;
  printf("collaps\n");
  for (i=0; i<4;i++) {
    for (j=0; j<4; j++)
      printf("%d ", g->collapsedNodes[i][j]);
    printf("    %d\n", g->noOfCollapsedNodes[i]);
  }
  printf("\n");
}



/*int col( VHGraph *vhgraph)
{
  initializeGraph( &g);
  //fillGraph( &g);
  ReadVHGraph( vhgraph);
  // order 132 is important !!!
  if (testOne( &g) < 0) {
    printf( "ERROR CODE 1\n");
    return 0;
  }
  if (testThree( &g) < 0) {
    printf( "ERROR CODE 3\n");
    return 0;
  }
  if (testTwo( &g) < 0) {
    printf( "ERROR CODE 2\n");
    return 0;
  }

  if (findInitialCollapse( &g) == -1) {
    printf( "There are not normal collapse!\n");
    return 0;
  }
  output( &g);
  while (findNextCollapse( &g) != -1) {
    output( &g);
  }

  /*findInitialCollapse( &g);

  int i;
  for (i=0; i<3;i++)
    printf("%d", g.sequence[i]);
  printf("\n");

  printA( &g);
  printB( &g);

  printf( "*%d ", findNextCollapse( &g));

  for (i=0; i<3;i++)
    printf("%d", g.sequence[i]);
  printf("\n");

  
  printf( "*%d ", findNextCollapse( &g));

  for (i=0; i<3;i++)
    printf("%d", g.sequence[i]);
  printf("\n");


  printf( "*%d ", findNextCollapse( &g));

  for (i=0; i<3;i++)
    printf("%d", g.sequence[i]);
  printf("\n");


  return 0;
}*/

void initializeGraph(struct hypergraph *g)
{
  g->sequenceLength = 0;
  int i;
  for( i=0; i < MAX_NO_OF_NODES; i++)
    g->noOfRelatedNodes[i] = 0;
  for( i=0; i < MAX_NO_OF_NODES; i++)
    g->noOfCollapsedNodes[i] = 0;
}

/*void fillGraph( struct hypergraph *g)
{
  /*g->noOfNodes = 4;
  strcpy(g->nodeName[0], "n1");
  strcpy(g->nodeName[1], "n2");
  strcpy(g->nodeName[2], "n3");
  strcpy(g->nodeName[3], "n4");
  
  g->noOfEdges = 3;
  g->edgeDimension[0] = 2;
  g->edgeDimension[1] = 2;
  g->edgeDimension[2] = 3;
  g->edge[0][0] = 0;  g->edge[0][1] = 3;
  g->edge[1][0] = 0;  g->edge[1][1] = 1;
  g->edge[2][0] = 0;  g->edge[2][1] = 1;  g->edge[2][2] = 2;
  strcpy(g->edgeName[0], "e1");
  strcpy(g->edgeName[1], "e2");
  strcpy(g->edgeName[2], "e3");*/

  /*g->noOfNodes = 10;
  strcpy(g->nodeName[0], "n1");
  strcpy(g->nodeName[1], "n2");
  strcpy(g->nodeName[2], "n3");
  strcpy(g->nodeName[3], "n4");
  strcpy(g->nodeName[4], "n5");
  strcpy(g->nodeName[5], "n6");
  strcpy(g->nodeName[6], "n7");
  strcpy(g->nodeName[7], "n8");
  strcpy(g->nodeName[8], "n9");
  strcpy(g->nodeName[9], "n10");
  
  g->noOfEdges = 9;
  g->edgeDimension[0] = 2;
  g->edgeDimension[1] = 3;
  g->edgeDimension[2] = 4;
  g->edgeDimension[3] = 5;
  g->edgeDimension[4] = 6;
  g->edgeDimension[5] = 7;
  g->edgeDimension[6] = 2;
  g->edgeDimension[7] = 2;
  g->edgeDimension[8] = 3;
  g->edge[0][0] = 0;  g->edge[0][1] = 1;
  g->edge[1][0] = 0;  g->edge[1][1] = 1;  g->edge[1][2] = 2;
  g->edge[2][0] = 0;  g->edge[2][1] = 1;  g->edge[2][2] = 2;  g->edge[2][3] = 3;
  g->edge[3][0] = 0;  g->edge[3][1] = 1;  g->edge[3][2] = 2;  g->edge[3][3] = 3;
   g->edge[3][4] = 4;
  g->edge[4][0] = 0;  g->edge[4][1] = 1;  g->edge[4][2] = 2;  g->edge[4][3] = 3;
   g->edge[4][4] = 4;  g->edge[4][5] = 5;
  g->edge[5][0] = 0;  g->edge[5][1] = 1;  g->edge[5][2] = 2;  g->edge[5][3] = 3;
   g->edge[5][4] = 4;  g->edge[5][5] = 5;  g->edge[5][6] = 6;
  g->edge[6][0] = 7;  g->edge[6][1] = 8;
  g->edge[7][0] = 5;  g->edge[7][1] = 8;
  g->edge[8][0] = 5;  g->edge[8][1] = 8;  g->edge[8][2] = 9;

  strcpy(g->edgeName[0], "e1");
  strcpy(g->edgeName[1], "e2");
  strcpy(g->edgeName[2], "e3");
  strcpy(g->edgeName[3], "e4");
  strcpy(g->edgeName[4], "e5");
  strcpy(g->edgeName[5], "e6");
  strcpy(g->edgeName[6], "e7");
  strcpy(g->edgeName[7], "e8");
  strcpy(g->edgeName[8], "e9");
}*/

int testOne( struct hypergraph *g) // connectivity
{
  return 1; // allways yes  TODO!
}

int testTwo( struct hypergraph *g) // 2D edge exist
{
  return findNext2DEdge( -1, g);
}

int testThree( struct hypergraph *g) // V = H + 1
{
  if (g->noOfNodes - 1 != g->noOfEdges)
    return -1; // negative
  else
    return 1; // positive
}

int findNext2DEdge( int seed, struct hypergraph *g)
{
  int dim;
  int i, j, k, l;
  int temp[MAX_NO_OF_NODES];

  if (seed == g->noOfEdges)
    return -1;

  for (i=seed+1; i < g->noOfEdges; i++) 
    {
      dim = 0;
      for (j=0; j < g->edgeDimension[i]; j++)
	temp[j] = g->edge[i][j];
      for (j=0; j < g->edgeDimension[i]; j++) 
	{
	  for (k=j+1; k < g->edgeDimension[i]; k++) 
	    {
	      for (l=0; l < g->noOfRelatedNodes[ temp[j] ]; l++) 
		{
		  if (temp[k] == g->relatedNodes[ temp[j] ][ l ])
		    temp[k] = temp[j];
		} // l
	    } // k
	} // j
      for (j=0; j < g->edgeDimension[i]; j++) 
	{
	  if (temp[j] != -1) 
	    {
	      dim++;
	      for (k=j+1; k < g->edgeDimension[i]; k++) 
		{
		  if (temp[j] == temp[k])
		    temp[k] = -1;
		} // k
	    } // if
	} // j
      if (dim == 2)
	return i;
    } // i
  
  return -1;
}

int findInitialCollapse( struct hypergraph *g)
{
  int i, e, j;

  e = findNext2DEdge( -1, g);
  for (i=0; i < g->noOfEdges && e != -1; i++)
    {
      for (j=0; j < g->noOfRelatedNodes[ g->edge[e][0] ]; j++)
	g->collapsedNodes[ i ][ g->noOfCollapsedNodes[i]++ ] =
	  g->relatedNodes[ g->edge[e][0] ][ j ];
      g->collapsedNodes[ i ][ g->noOfCollapsedNodes[i]++ ] = g->edge[e][0];
      collapse2DEdge( e, g);
      g->sequence[g->sequenceLength++] = e;
      e = findNext2DEdge( -1, g);    
    }

  if (g->sequenceLength == g->noOfEdges)
    return 1;
  else
    return -1;
}

void collapse2DEdge( int e, struct hypergraph *g)
{
  int i, j, k, flag, one, another, noOfNodesInHypernode;
  int temp[MAX_NO_OF_NODES];

  one = 0;
  another = 0;
  do {
    another++;
    flag = 0;
    for (i=0; i < g->noOfRelatedNodes[ g->edge[e][one] ]; i++)
      {
	if ( g->relatedNodes[ g->edge[e][one] ][ i ] == g->edge[e][another])
	  flag = 1;
      }
  } while (flag);

  one = g->edge[e][one];
  another = g->edge[e][another];
  noOfNodesInHypernode = 0;
  temp[noOfNodesInHypernode++] = one;
  for (i=0; i < g->noOfRelatedNodes[one]; i++)
    temp[noOfNodesInHypernode++] = g->relatedNodes[one][i];
  temp[noOfNodesInHypernode++] = another;
  for (i=0; i < g->noOfRelatedNodes[another]; i++)
    temp[noOfNodesInHypernode++] = g->relatedNodes[another][i];

  for (i=0; i < noOfNodesInHypernode; i++)
    {
      for (j=0,k=0; j < noOfNodesInHypernode; j++)
	{
	  if (temp[i] != temp[j])
	    {
	      g->relatedNodes[ temp[i] ][ k++ ] = temp[j];
	    }
	} // j
      g->noOfRelatedNodes[ temp[i] ] = k;
    } // i
}

int findNextCollapse( struct hypergraph *g)
{
  int *i, j, e, next_e;

  i = &g->sequenceLength;
  
  do
    {
      do
	{
	  e = g->sequence[ *i - 1 ];
	  decollapseLast2DEdge( g);
	  next_e = findNext2DEdge( e, g);
	
	  //printA(g);
      //printB(g);

	}
      while (next_e == -1 && *i > 0);
      if (next_e == -1 && *i == 0)
	return -1;
      e = next_e;
      //printf( "^%d\n", e );
      do
	{
	  g->noOfCollapsedNodes[*i] = 0;
	  for (j=0; j < g->noOfRelatedNodes[ g->edge[e][0] ]; j++)
	    g->collapsedNodes[ *i ][ g->noOfCollapsedNodes[*i]++ ] =
	      g->relatedNodes[ g->edge[e][0] ][ j ];
	  g->collapsedNodes[ *i ][ g->noOfCollapsedNodes[*i]++ ] = g->edge[e][0];
	  collapse2DEdge( e, g);
	  g->sequence[(*i)++] = e;
	  //printA(g);
	  //printB(g);
	  e = findNext2DEdge( -1, g);
	  //printf( "^%d\n", e );
	}
	while (e != -1);
    }
  while (*i < g->noOfEdges);
  
  return 1;
}

void decollapseLast2DEdge( struct hypergraph *g)
{
  int i, j, k, l1, l2, l, flag, e;
  int *one, two[MAX_NO_OF_NODES], both[MAX_NO_OF_NODES];

  e = g->sequence[ --g->sequenceLength ];
  one = g->collapsedNodes[ g->sequenceLength ];
  l1 = g->noOfCollapsedNodes[g->sequenceLength];

  for (l=0; l < g->noOfRelatedNodes[ g->edge[e][0] ]; l++)
    {
      both[l] = g->relatedNodes[ g->edge[e][0] ][ l ];
    }
  both[l++] = g->edge[e][0];

  for (i=0,l2=0; i < l; i++)
    {
      flag = 0;
      for (j=0; j < l1; j++)
	{
	  if ( both[ i ] == one[ j ])
	    flag = 1;
	} // j
      if (flag == 0)
	two[l2++] = both[ i ];
    } // i

  for (i=0; i < l1; i++)
    {
      for (j=0,k=0; j < l1; j++)
	{
	  if (i != j)
	    g->relatedNodes[ one[i] ][ k++ ] = one[j];
	}
      g->noOfRelatedNodes[ one[i] ] = l1 - 1;
    }
  for (i=0; i < l2; i++)
    {
      for (j=0,k=0; j < l2; j++)
	{
	  if (i != j)
	    g->relatedNodes[ two[i] ][ k++ ] = two[j];
	}
      g->noOfRelatedNodes[ two[i] ] = l2 - 1;
    }

}

void output( struct hypergraph *g)
{
  int i;

  for(i=0; i < g->noOfEdges; i++)
    printf("%d ", g->edgeName[g->sequence[i]]);
  printf("\n");
}


void putCollapseInSequence( struct hypergraph *g)
{
	int i, hNodeNum;
	
	history.push_back( vector<int>());
	for (i=0; i < g->noOfEdges; i++) {
		hNodeNum = g->edgeName[ g->sequence[i] ];
		history.back().push_back( hNodeNum);
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void ReadVHGraph( VHGraph *vhgraph)
{
	int i, j, k;

	initializeGraph( &g);
	sequenceIndex = 0;
	history.clear();

	list <int> nodeList = vhgraph->GetAllNodeList();
	g.noOfNodes = (int)nodeList.size( );

	list <int> edgeList = vhgraph->GetAllEdgeList();
	g.noOfEdges = (int)edgeList.size( );
	
	list<int>::const_iterator it;
	for( it = nodeList.begin(), i=0;
		 it != nodeList.end();
		 ++it, i++ )
	{
		snprintf( g.nodeName[i], MAX_LENGTH_OF_TITLE, "%d", *it);
	}
	
	list <int> nodeOfEdgeList;
	list<int>::const_iterator iter;
	list<int>::const_iterator iterat;
	for( it = edgeList.begin(), i=0;
		 it != edgeList.end();
		 ++it, i++ )
	{
		g.edgeName[i] = *it;
		//snprintf( g.edgeName[i], MAX_LENGTH_OF_TITLE, "%d", i+1); //vhgraph->FindHEdgeByNum( *it )->print_name);
		nodeOfEdgeList = vhgraph->GetEdgeNodeList(*it);
		g.edgeDimension[i] = (int)nodeOfEdgeList.size( );
		for( iter = nodeOfEdgeList.begin(), j=0;
			 iter != nodeOfEdgeList.end();
			 ++iter, j++)
		{
			for( iterat = nodeList.begin(), k=0;
				 *iterat != *iter;
				 ++iterat, k++ );
			g.edge[i][j] = k;
		}
	}
} /* ReadVHGraph */

int RunBCollapsAlgo()
{
	int i;
	
	if (testOne( &g) < 0) {
		printf( "ERROR CODE 1\n");
		return 0;
    }
    if (testThree( &g) < 0) {
		printf( "ERROR CODE 3\n");
		return 0;
    }
    if (testTwo( &g) < 0) {
		printf( "ERROR CODE 2\n");
		return 0;
    }

	if (findInitialCollapse( &g) == -1) {
		printf( "There are not normal collapse!\n");
		return 0;
    }
	putCollapseInSequence( &g);
	output( &g);
    for (i=1; findNextCollapse( &g) != -1; i++) {
		putCollapseInSequence( &g);
		output( &g);
    }
	return i;
} /* RunBCollapsAlgo */

void SelectCollapse( int serNum)
{
	if (serNum != serialNumber && sequenceIndex != 0) {
		printf("sequenceIndex != 0 in function SelectCollapse");
		exit(-1);
	}
	serialNumber = serNum;
} /* SelectCollapse */

string GetCollapseSelectName( int serialNumber)
{
	ostringstream res;
	unsigned int i;

	res << history[serialNumber][0];
	for (i=1; i < history[serialNumber].size(); i++)
		res << " " << history[serialNumber][i];
	return res.str();
} /* GetCollapseSelectName */

void DrawNext(VHGraph *vhgraph)
{
	if (sequenceIndex < g.noOfEdges) {
		vhgraph->CollapseEdge( history[serialNumber][sequenceIndex] );
		sequenceIndex++;
	}
	else
		printf("No more edges!\n");
}

void DrawPrev(VHGraph *vhgraph)
{
	if (sequenceIndex > 0) {
		vhgraph->UndoCollapse();
		sequenceIndex--;
	}
	else
		printf("It's a beginning!\n");
}




